use crate::src::struct_and_type::{
    BinomialHeap, BinomialHeapCompareFunc, BinomialHeapType, BinomialHeapValue, BinomialTree,
};
use :: libc;
extern "C" {
    fn malloc(_: u64) -> *mut libc::c_void;
    fn calloc(_: u64, _: u64) -> *mut libc::c_void;
    fn free(_: *mut libc::c_void);
    fn memcpy(_: *mut libc::c_void, _: *const libc::c_void, _: u64) -> *mut libc::c_void;
}
pub const BINOMIAL_HEAP_TYPE_MAX: BinomialHeapType = 1;
pub const BINOMIAL_HEAP_TYPE_MIN: BinomialHeapType = 0;
extern "C" fn binomial_heap_cmp(
    mut heap: *mut BinomialHeap,
    mut data1: BinomialHeapValue,
    mut data2: BinomialHeapValue,
) -> i32 {
    if (unsafe { (*heap).heap_type }) as u32 == BINOMIAL_HEAP_TYPE_MIN as i32 as u32 {
        return unsafe { ((*heap).compare_func).expect("non-null function pointer")(data1, data2) };
    } else {
        return -(unsafe {
            ((*heap).compare_func).expect("non-null function pointer")(data1, data2)
        });
    };
}
extern "C" fn binomial_tree_ref(mut tree: *mut BinomialTree) {
    if !tree.is_null() {
        (unsafe { (*tree).refcount = ((*tree).refcount).wrapping_add(1) });
        (unsafe { (*tree).refcount });
    }
}
extern "C" fn binomial_tree_unref(mut tree: *mut BinomialTree) {
    let mut i: i32 = 0;
    if tree.is_null() {
        return;
    }
    (unsafe { (*tree).refcount = ((*tree).refcount).wrapping_sub(1) });
    (unsafe { (*tree).refcount });
    if (unsafe { (*tree).refcount }) as i32 == 0 as i32 {
        i = 0 as i32;
        while i < (unsafe { (*tree).order }) as i32 {
            binomial_tree_unref(unsafe { *((*tree).subtrees).offset(i as isize) });
            i += 1;
            i;
        }
        (unsafe { free((*tree).subtrees as *mut libc::c_void) });
        (unsafe { free(tree as *mut libc::c_void) });
    }
}
extern "C" fn binomial_tree_merge(
    mut heap: *mut BinomialHeap,
    mut tree1: *mut BinomialTree,
    mut tree2: *mut BinomialTree,
) -> *mut BinomialTree {
    let mut new_tree: *mut BinomialTree = 0 as *mut BinomialTree;
    let mut tmp: *mut BinomialTree = 0 as *mut BinomialTree;
    let mut i: i32 = 0;
    if binomial_heap_cmp(heap, unsafe { (*tree1).value }, unsafe { (*tree2).value }) > 0 as i32 {
        tmp = tree1;
        tree1 = tree2;
        tree2 = tmp;
    }
    new_tree =
        (unsafe { malloc(::core::mem::size_of::<BinomialTree>() as u64) }) as *mut BinomialTree;
    if new_tree.is_null() {
        return 0 as *mut BinomialTree;
    }
    (unsafe { (*new_tree).refcount = 0 as i32 as u16 });
    (unsafe { (*new_tree).order = ((*tree1).order as i32 + 1 as i32) as u16 });
    (unsafe { (*new_tree).value = (*tree1).value });
    (unsafe {
        (*new_tree).subtrees = malloc(
            (::core::mem::size_of::<*mut BinomialTree>() as u64)
                .wrapping_mul((*new_tree).order as u64),
        ) as *mut *mut BinomialTree
    });
    if (unsafe { (*new_tree).subtrees }).is_null() {
        (unsafe { free(new_tree as *mut libc::c_void) });
        return 0 as *mut BinomialTree;
    }
    (unsafe {
        memcpy(
            (*new_tree).subtrees as *mut libc::c_void,
            (*tree1).subtrees as *const libc::c_void,
            (::core::mem::size_of::<*mut BinomialTree>() as u64)
                .wrapping_mul((*tree1).order as u64),
        )
    });
    let fresh0 = unsafe {
        &mut (*((*new_tree).subtrees).offset(((*new_tree).order as i32 - 1 as i32) as isize))
    };
    *fresh0 = tree2;
    i = 0 as i32;
    while i < (unsafe { (*new_tree).order }) as i32 {
        binomial_tree_ref(unsafe { *((*new_tree).subtrees).offset(i as isize) });
        i += 1;
        i;
    }
    return new_tree;
}
extern "C" fn binomial_heap_merge_undo(mut new_roots: *mut *mut BinomialTree, mut count: u32) {
    let mut i: u32 = 0;
    i = 0 as i32 as u32;
    while i <= count {
        binomial_tree_unref(unsafe { *new_roots.offset(i as isize) });
        i = i.wrapping_add(1);
        i;
    }
    (unsafe { free(new_roots as *mut libc::c_void) });
}
extern "C" fn binomial_heap_merge(
    mut heap: *mut BinomialHeap,
    mut other: *mut BinomialHeap,
) -> i32 {
    let mut new_roots: *mut *mut BinomialTree = 0 as *mut *mut BinomialTree;
    let mut new_roots_length: u32 = 0;
    let mut vals: [*mut BinomialTree; 3] = [0 as *mut BinomialTree; 3];
    let mut num_vals: i32 = 0;
    let mut carry: *mut BinomialTree = 0 as *mut BinomialTree;
    let mut new_carry: *mut BinomialTree = 0 as *mut BinomialTree;
    let mut max: u32 = 0;
    let mut i: u32 = 0;
    if (unsafe { (*heap).roots_length }) > (unsafe { (*other).roots_length }) {
        max = (unsafe { (*heap).roots_length }).wrapping_add(1 as i32 as u32);
    } else {
        max = (unsafe { (*other).roots_length }).wrapping_add(1 as i32 as u32);
    }
    new_roots = (unsafe {
        malloc((::core::mem::size_of::<*mut BinomialTree>() as u64).wrapping_mul(max as u64))
    }) as *mut *mut BinomialTree;
    if new_roots.is_null() {
        return 0 as i32;
    }
    new_roots_length = 0 as i32 as u32;
    carry = 0 as *mut BinomialTree;
    i = 0 as i32 as u32;
    while i < max {
        num_vals = 0 as i32;
        if i < (unsafe { (*heap).roots_length })
            && !(unsafe { *((*heap).roots).offset(i as isize) }).is_null()
        {
            vals[num_vals as usize] = unsafe { *((*heap).roots).offset(i as isize) };
            num_vals += 1;
            num_vals;
        }
        if i < (unsafe { (*other).roots_length })
            && !(unsafe { *((*other).roots).offset(i as isize) }).is_null()
        {
            vals[num_vals as usize] = unsafe { *((*other).roots).offset(i as isize) };
            num_vals += 1;
            num_vals;
        }
        if !carry.is_null() {
            vals[num_vals as usize] = carry;
            num_vals += 1;
            num_vals;
        }
        if num_vals & 1 as i32 != 0 as i32 {
            let fresh1 = unsafe { &mut (*new_roots.offset(i as isize)) };
            *fresh1 = vals[(num_vals - 1 as i32) as usize];
            binomial_tree_ref(unsafe { *new_roots.offset(i as isize) });
            new_roots_length = i.wrapping_add(1 as i32 as u32);
        } else {
            let fresh2 = unsafe { &mut (*new_roots.offset(i as isize)) };
            *fresh2 = 0 as *mut BinomialTree;
        }
        if num_vals & 2 as i32 != 0 as i32 {
            new_carry = binomial_tree_merge(heap, vals[0 as i32 as usize], vals[1 as i32 as usize]);
            if new_carry.is_null() {
                binomial_heap_merge_undo(new_roots, i);
                binomial_tree_unref(carry);
                return 0 as i32;
            }
        } else {
            new_carry = 0 as *mut BinomialTree;
        }
        binomial_tree_unref(carry);
        carry = new_carry;
        binomial_tree_ref(carry);
        i = i.wrapping_add(1);
        i;
    }
    i = 0 as i32 as u32;
    while i < (unsafe { (*heap).roots_length }) {
        if !(unsafe { *((*heap).roots).offset(i as isize) }).is_null() {
            binomial_tree_unref(unsafe { *((*heap).roots).offset(i as isize) });
        }
        i = i.wrapping_add(1);
        i;
    }
    (unsafe { free((*heap).roots as *mut libc::c_void) });
    (unsafe { (*heap).roots = new_roots });
    (unsafe { (*heap).roots_length = new_roots_length });
    return 1 as i32;
}
#[no_mangle]
pub extern "C" fn binomial_heap_new(
    mut heap_type: BinomialHeapType,
    mut compare_func: BinomialHeapCompareFunc,
) -> *mut BinomialHeap {
    let mut new_heap: *mut BinomialHeap = 0 as *mut BinomialHeap;
    new_heap = (unsafe {
        calloc(
            1 as i32 as u64,
            ::core::mem::size_of::<BinomialHeap>() as u64,
        )
    }) as *mut BinomialHeap;
    if new_heap.is_null() {
        return 0 as *mut BinomialHeap;
    }
    (unsafe { (*new_heap).heap_type = heap_type });
    (unsafe { (*new_heap).compare_func = compare_func });
    return new_heap;
}
#[no_mangle]
pub extern "C" fn binomial_heap_free(mut heap: *mut BinomialHeap) {
    let mut i: u32 = 0;
    i = 0 as i32 as u32;
    while i < (unsafe { (*heap).roots_length }) {
        binomial_tree_unref(unsafe { *((*heap).roots).offset(i as isize) });
        i = i.wrapping_add(1);
        i;
    }
    (unsafe { free((*heap).roots as *mut libc::c_void) });
    (unsafe { free(heap as *mut libc::c_void) });
}
#[no_mangle]
pub extern "C" fn binomial_heap_insert(
    mut heap: *mut BinomialHeap,
    mut value: BinomialHeapValue,
) -> i32 {
    let mut fake_heap: BinomialHeap = BinomialHeap {
        heap_type: BINOMIAL_HEAP_TYPE_MIN,
        compare_func: None,
        num_values: 0,
        roots: 0 as *mut *mut BinomialTree,
        roots_length: 0,
    };
    let mut new_tree: *mut BinomialTree = 0 as *mut BinomialTree;
    let mut result: i32 = 0;
    new_tree =
        (unsafe { malloc(::core::mem::size_of::<BinomialTree>() as u64) }) as *mut BinomialTree;
    if new_tree.is_null() {
        return 0 as i32;
    }
    (unsafe { (*new_tree).value = value });
    (unsafe { (*new_tree).order = 0 as i32 as u16 });
    (unsafe { (*new_tree).refcount = 1 as i32 as u16 });
    (unsafe { (*new_tree).subtrees = 0 as *mut *mut BinomialTree });
    fake_heap.heap_type = unsafe { (*heap).heap_type };
    fake_heap.compare_func = unsafe { (*heap).compare_func };
    fake_heap.num_values = 1 as i32 as u32;
    fake_heap.roots = &mut new_tree;
    fake_heap.roots_length = 1 as i32 as u32;
    result = binomial_heap_merge(heap, &mut fake_heap);
    if result != 0 as i32 {
        (unsafe { (*heap).num_values = ((*heap).num_values).wrapping_add(1) });
        (unsafe { (*heap).num_values });
    }
    binomial_tree_unref(new_tree);
    return result;
}
#[no_mangle]
pub extern "C" fn binomial_heap_pop(mut heap: *mut BinomialHeap) -> BinomialHeapValue {
    let mut least_tree: *mut BinomialTree = 0 as *mut BinomialTree;
    let mut fake_heap: BinomialHeap = BinomialHeap {
        heap_type: BINOMIAL_HEAP_TYPE_MIN,
        compare_func: None,
        num_values: 0,
        roots: 0 as *mut *mut BinomialTree,
        roots_length: 0,
    };
    let mut result: BinomialHeapValue = 0 as *mut libc::c_void;
    let mut i: u32 = 0;
    let mut least_index: u32 = 0;
    if (unsafe { (*heap).num_values }) == 0 as i32 as u32 {
        return 0 as *mut libc::c_void;
    }
    least_index = (2147483647 as i32 as u32)
        .wrapping_mul(2 as u32)
        .wrapping_add(1 as u32);
    i = 0 as i32 as u32;
    while i < (unsafe { (*heap).roots_length }) {
        if !(unsafe { *((*heap).roots).offset(i as isize) }).is_null() {
            if least_index
                == (2147483647 as i32 as u32)
                    .wrapping_mul(2 as u32)
                    .wrapping_add(1 as u32)
                || binomial_heap_cmp(
                    heap,
                    unsafe { (**((*heap).roots).offset(i as isize)).value },
                    unsafe { (**((*heap).roots).offset(least_index as isize)).value },
                ) < 0 as i32
            {
                least_index = i;
            }
        }
        i = i.wrapping_add(1);
        i;
    }
    least_tree = unsafe { *((*heap).roots).offset(least_index as isize) };
    let fresh3 = unsafe { &mut (*((*heap).roots).offset(least_index as isize)) };
    *fresh3 = 0 as *mut BinomialTree;
    fake_heap.heap_type = unsafe { (*heap).heap_type };
    fake_heap.compare_func = unsafe { (*heap).compare_func };
    fake_heap.roots = unsafe { (*least_tree).subtrees };
    fake_heap.roots_length = (unsafe { (*least_tree).order }) as u32;
    if binomial_heap_merge(heap, &mut fake_heap) != 0 {
        result = unsafe { (*least_tree).value };
        binomial_tree_unref(least_tree);
        (unsafe { (*heap).num_values = ((*heap).num_values).wrapping_sub(1) });
        (unsafe { (*heap).num_values });
        return result;
    } else {
        let fresh4 = unsafe { &mut (*((*heap).roots).offset(least_index as isize)) };
        *fresh4 = least_tree;
        return 0 as *mut libc::c_void;
    };
}
#[no_mangle]
pub extern "C" fn binomial_heap_num_entries(mut heap: *mut BinomialHeap) -> u32 {
    return unsafe { (*heap).num_values };
}
